<head>
    <meta charset="UTF-8">
<title>算法提高 转圈游戏</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div class="column">
<p><span style="font-size: 15px;">【问题描述】</span></p>
<p><span style="font-size: 15px;">n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从</span><span style="font-size: 15px;">0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,......,依此类 推。</span></p>
<p><span style="font-size: 15px;">游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小 伙伴走到第 m+1 号位置,......,依此类推,第n &minus; m号位置上的小伙伴走到第 0 号位置,第 n-m+1 号位置上的小伙伴走到第 1 号位置,......,第 n-1 号位置上的小伙伴顺时针走到第 m-1 号位置。</span></p>
<p><span style="font-size: 15px;">现在,一共进行了 10<sup>k</sup> 轮,请问 x 号小伙伴最后走到了第几号位置。</span></p>
<p><span style="font-size: 15px;">【输入】</span></p>
<p><span style="font-size: 15px;">输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。&nbsp;</span></p>
<p>【输出】</p>
<p>输出共 1 行,包含 1 个整数,表示 10<sup>k</sup> 轮后 x 号小伙伴所在的位置编号。</p>
<p><span style="font-size: 15px;">【输入样例】</span></p>
<div>
<p>￼10 3 4 5</p>
<p><span style="font-size: 15px;">【输出样例】</span></p>
</div>
<div><span style="font-size: 15px;">5</span></div>
<p><span style="font-size: 15px;">【数据范围】</span></p>
<p><span style="font-size: 15px;">对于 30%的数据,0 &lt; k &lt; 7;</span></p>
<p><span style="font-size: 15px;">对于 80%的数据,0 &lt; k &lt; 10<sup>7</sup>;</span></p>
<p><span style="font-size: 15px;">对于 100%的数据,1 &lt; n &lt; 1,000,000,0 &lt; m &lt; n,1 &le; x &le; n,0 &lt; k &lt; 10<sup>9</sup>。&nbsp;</span></p>
<div>&nbsp;</div>
</div>